发布时间 : 星期三 文章数据结构（本）期末综合练习（2013年6月）更新完毕开始阅读
q=p; x=p->data;
while （q->next!=NULL）q=q->next; __(1)___
q=p; p=p->next; while(p->data!=x) { q=p; __(2)___ }
__(3)___
期末综合练习一答案：
一、单项选择题
1．B 2．C 3．A 4．A 5．C 6．A 7．A 812．C 13．D 14．C 15．C 16．D 17．C 1821．D 22．A 23．A 24．B 25．A 26．C 27
二、填空题 1．逻辑
2．物理（存储）
3．元素间的比较 O(n) 4．乘法 O(n3) 5．25 6．8
7．p->next=q；
8． 直接前驱的左指针 9．p->next=p->next->next; 10． p->next= head;
11．p->next=top; top=p；
12．d=top->data;top=top->next; 13．front->next
14．front= =(rear+1)% MaxSize 15．7 16．34 17．5 18．15 19．15 20．1
21．512389746 22．215347896 23．不正确 24．主关键字
三、综合应用题 1．(1)
．C 9．A 10．C 19．C 20．B 28．B 29
．D 11．C ．B
．A 30．C 9
39
2217
12108 9
7 5
3 4
图7
(2)
3 0000 4 0001 5 001 10 01 8 10 9 11
（3）n个，因为非叶结点数比叶结点数少一个,而权值个数=叶结点数
2. (1)
23
9
8645
44
3 1
图8
（2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58
(3) 共11个结点,22个指针域,除根结点外,每个结点对应一个指针域.,共10个指针域非空,故 有 22-10=12个空指针域,
10
143. (1) 循环执行以下两步
选择一个度为0的顶点并输出 从网中删除此结点及所有出边
（2） 因为选择一个度为0的顶点时不一定是唯一的
（3） 由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱
(4) 152364 152634 156234 4 .
(1) A1 A2 A4 A7 A8 A5 A9 A3 A6 (2) (3)
7 4 8 2 5 9 1 3 6 3.5 图9 5.
（1) 5
(2)
26 2329
21242731
2225283032
图10 (3) 3
(4) ASL=(1+2*2+3*4+5*4)/12=37/12
11
6.(1)
9 6 12 5 7 10 13 8 11 14 图10
(2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树 非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子 树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值; 左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。 (3) 3次
四、程序填空题 1.(1) i++; (2) i ++; (3) a[j]=a[i]; (4) j--;
(5) (a, i+1,end); 2．（1）n-1
（2）n （3）k=j
（4）a[i]=a[k] （5）a[k]=temp 3．
（1）malloc(sizeof (struct node)) （2）rear->next=p （3）p
4.
(1) q->next=head;
(2) p=p->next; (3) q->next=p->next;
12